package Sort;

/**
 * 排序(6)
 * 归并排序
 * 简单概述：待排序序列分为若干个子序列，使每个子序列是有序的，然后再把有序子序列合并为整体有序序列。
 */
public class MergeSort extends Template {

    //算法4  P170
    private static Comparable[] tempArr;

    /**
     * 归并排序
     *
     * @param a 需排序的数组
     */
    public static void sort(Comparable[] a) {
        tempArr = new Comparable[a.length];//初始化一个临时数组 暂时保存数据
        MergeSort.sort(a, 0, a.length - 1);
    }

    /**
     * 归并排序
     *
     * @param a    需排序的数组
     * @param low  a的第一个下标
     * @param high a的最后一个下标
     */
    public static void sort(Comparable[] a, int low, int high) {
        if (high <= low) return;
        int middle = low + (high - low) / 2;//low至high的中间坐标 偶数取靠前
        //System.out.println("本次归并的中间下标" + middle);
        sort(a, low, middle);//左半边归并排序
        sort(a, middle + 1, high);//右半边归并排序
        merge(a, low, middle, high);//两边均有序后合并数组 a[low]到a[middle] a[middle+1]到a[high]两数组
    }

    /**
     * 将a[low]到a[middle] a[middle+1]到a[high]两数组
     * 归并至a[low]至a[high]中
     *
     * @param a      需要归并排序的原始数组
     * @param low    a的第一个下标
     * @param middle a的中间下标
     * @param high   a的最后一个下标
     */
    private static void merge(Comparable[] a, int low, int middle, int high) {
        int i = low, j = middle + 1;
        for (int k = low; k <= high; k++) tempArr[k] = a[k];//将a复制到tempArr中

        //归并过程
        for (int k = low; k <= high; k++) {
            if (i > middle) a[k] = tempArr[j++];
            else if (j > high) a[k] = tempArr[i++];
            else if (less(tempArr[j], tempArr[i])) a[k] = tempArr[j++];
            else a[k] = tempArr[i++];
        }
    }

//以下代码来自博客https://blog.csdn.net/u012562943/article/details/10013653
// 缺点 没有一次性分配辅助数组的空间
//    //升序
//    public static void sort(Comparable[] element, int left, int right) {
//        if (left < right) {
//            int mid = (left + right) / 2;//左边进行递归排序
//            sort(element, left, mid);//右边进行递归排序
//            sort(element, mid + 1, right);//左右两部分进行合并处理
//            merge(element, left, mid, right);
//        }
//    }

    //两相邻有序子数组的归并
//    public static void merge(Comparable[] element, int left, int middle, int right) {
//        Comparable[] tmpElement = new Comparable[element.length];
//        int index = left, tmpIndex = left;
//        int mid = middle + 1;
//        while (left <= middle && mid <= right) {
//            if (less(element[left], element[mid])) tmpElement[index++] = element[left++];//element[left] <= element[mid]
//            else tmpElement[index++] = element[mid++];
//        }
//        while (left <= middle) tmpElement[index++] = element[left++];
//        while (mid <= right) tmpElement[index++] = element[mid++];
//        while (tmpIndex <= right) element[tmpIndex] = tmpElement[tmpIndex++];
//    }

    public static void main(String[] args) {
        //Comparable[] a = Template.getData(9);
        Comparable[] a = {23, 77, 28, 30, 71, 3, 74, 73, 62, 9};
        System.out.println("归并排序前");

        show(a);

        //System.out.println("归并排序过程");
        sort(a);

        assert isSorted(a);
        System.out.println("归并排序后");
        show(a);
    }

}
